package BinarySearch;

/**
 *
 * @Input: [1, 2, 3, 4, 5]
 * @Key: 3
 * @return: [Index: 2]
 */
public class binarySearchDemo {
    /**
     * Basic Binary Search
     * @param nums
     * @param target
     * @return Index
     */
    public int binarySearch(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }

    /**
     * 在一个有重复的数组中找到Key的最左位置
     *
     */
    public int binarySearchI(int[] nums, int target) {
        int l = 0;
        int h = nums.length - 1;
        while (l < h) {
            int middle = l + (h - l) / 2;
            if (nums[middle] >= target) {
                h = middle;
            } else {
                l = middle + 1;
            }
        }
        return l;
    }
}
